#include <iostream>
#include <cstdlib>
#include<limits>

#define RED true
#define BLACK false
#define MIN (std::numeric_limits<T>::min())

template<typename T>

class BinaryTree
{
public:
    class Node
    {
        public:
        T data;
        Node* lc;
        Node* rc;
        Node* parent;
        bool color;
        Node(){color = RED;};
        Node(T _data)
        {
            data = _data;
            lc = rc = parent = NULL;
            color = RED;
        };
    };

protected:
    Node* root;
    Node* nil;
    void transplant(Node* _u, Node* _v);
    void RightRotate(Node* _x);
    void LeftRotate(Node* _x);
    ~BinaryTree();
    void inorder_walk(Node* _x) const;
    void release(Node* _x);
    Node* successor(Node* _x) const;
    Node* predecessor(Node* _x) const;
    Node* min(Node* _x) const;
    Node* max(Node* _x) const;

public:
    BinaryTree() 
    {
        nil = new Node;
        nil->color = BLACK;
        nil->data = MIN;
        root = nil;
    };
    BinaryTree(T _data)
    {
        nil = new Node;
        nil->color = BLACK;
        nil->data = MIN;
        Node *r = new Node;
        r->data = _data;
        r->lc = r->rc = r->parent = nil;
        r->color = BLACK;
        root = r;
    };
    void insert(Node* _x);
    void insert(T _data);
    Node* tree_search(T _data);
    void inorder_walk() const;
    void tree_delete(Node* _x);
};


template<typename T>
void BinaryTree<T>::release(Node* _x)
{
    if(_x != NULL)
    {
        release(_x->lc);
        release(_x->rc);
        delete _x;
    }
};

template<typename T>
BinaryTree<T>::~BinaryTree()
{
    release(root);
};

template<typename T>
void BinaryTree<T>::insert(Node* _x)
{
    Node* y = this->nil;
    Node* x = this->root;
    _x->lc = _x->rc = this->nil;
    while(x != this->nil)
    {
        y = x;
        if(_x->data < x->data)
            x = x->lc;
        else
            x = x->rc;
    }
    _x->parent = y;
    if(y == this->nil)
        this->root = _x;
    else if(_x->data < y->data)
        y->lc = _x;
    else
    {
        y->rc = _x;
    }
    
};

template<typename T>
void BinaryTree<T>::insert(T _data)
{
    Node* y = this->nil;
    Node* x = this->root;
    Node* p = new Node(_data);
    p->lc = p->rc = this->nil;
    while (x != this->nil)
    {
        y = x;
        if(p->data < y->data)
            x = x->lc;
        else
            x = x->rc;
    }
    p->parent = y;
    if (y == this->nil)
        this->root = p;
    else if (p->data < y->data)
        y->lc = p;
    else
        y->rc = p;
};

template<typename T>
typename BinaryTree<T>::Node* BinaryTree<T>::tree_search(T _data)
{
    Node* x = root;
    while(x != NULL && x->data != _data)
    {
        if(_data < x->data)
        x = x->lc;
        else
        x = x->rc;
    }
    if( x == NULL)
    {
        std::cout << "Not Found" << std::endl;
        return NULL;
    }
    else
    {
        return x;
    }
};

template<typename T>
void BinaryTree<T>::inorder_walk(Node* _x) const
{
    if (_x != NULL)
    {
        inorder_walk(_x->lc);
        std::cout << _x->data << "\t";
        inorder_walk(_x->rc);
    }
};

template<typename T>
void BinaryTree<T>::inorder_walk() const
{
    inorder_walk(root);
    std::cout << std::endl;
};

template<typename T>
typename BinaryTree<T>::Node* BinaryTree<T>::min(Node* _x) const
{
    while(_x->lc != NULL)
    {
        _x = _x->lc;
    }
    return _x;
};

template<typename T>
typename BinaryTree<T>::Node* BinaryTree<T>::max(Node* _x) const
{
    while(_x->rc != NULL)
    {
        _x = _x->rc;
    }
    return _x;
};

template<typename T>
typename BinaryTree<T>::Node* BinaryTree<T>::successor(Node* _x) const
{
    Node* x = _x;
    if (x->rc != NULL)
    return min(x->rc);
    Node* y = _x->parent;
    while(y != NULL && x == y->rc)
    {
        x = y;
        y = x->parent;
    }
    return y;
};

template<typename T>
typename BinaryTree<T>::Node* BinaryTree<T>::predecessor(Node* _x) const
{
    Node* x = _x;
    if (x->lc != NULL)
    return max(x->lc);
    Node* y = _x->parent;
    while(y != NULL && x == y->lc)
    {
        x = y;
        y = x->parent;
    }
    return y;
};

template<typename T>
void BinaryTree<T>::transplant(Node* _u, Node* _v)      //use _v replace _u
{
    if(_u->parent == this->nil)
    root = _v;
    else if (_u == _u->parent->lc)
    _u->parent->lc = _v;
    else
    _u->parent->rc = _v;
    _v->parent = _u->parent;
};

template<typename T>
void BinaryTree<T>::tree_delete(Node* _x)
{
    if(_x->lc == nil)
    transplant(_x, _x->rc);
    else if(_x->rc == nil)
    transplant(_x, _x->lc);
    else
    {
        Node* y = successor(_x);
        if(y->parent != _x)
        {
            transplant(y, y->rc);
            y->rc = _x->rc;
            y->rc->parent = y;
        }
        transplant(_x, y);
        y->lc == _x->lc;
        y->lc->parent = y;
    }
};

template<typename T>
void BinaryTree<T>::RightRotate(Node* _x)
{
    Node* y = _x->lc;
    _x->lc = y->rc;
    if(y->rc != nil)
        y->rc->parent = _x;
    if(_x->parent == nil)
        root = y;
    else if (_x == _x->parent->lc)
        _x->parent->lc = y;
    else
        _x->parent->rc = y;
    y->rc = _x;
    _x->parent = y;
};

template<typename T>
void BinaryTree<T>::LeftRotate(Node* _x)
{
    Node* y = _x->rc;
    _x->rc = y->lc;
    if(y->lc != nil)
        y->lc->parent = _x;
    y->parent = _x->parent;
    if(_x->parent == nil)
        root = y;
    else if (_x == _x->parent->lc)
        _x->parent->lc = y;
    else
        _x->parent->rc = y;
    y->lc = _x;
    _x->parent = y;
};